package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/6 7:09 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0865 {


    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return getNodes(root).node;
    }

    private NodeInfo getNodes(TreeNode node) {
        if (node == null) {
            return new NodeInfo(node, 0);
        }
        NodeInfo l = getNodes(node.left);
        NodeInfo r = getNodes(node.right);
        if (l.depth == r.depth) {
            return new NodeInfo(node, l.depth + 1);
        }
        if (l.depth > r.depth) {
            return new NodeInfo(l.node, l.depth + 1);
        }
        return new NodeInfo(r.node, r.depth + 1);
    }



    class NodeInfo {
        TreeNode node;
        int depth;
        NodeInfo(TreeNode node, int depth) {
            this.depth = depth;
            this.node = node;
        }
    }

//    作者：沪里户外
//    链接：https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/solutions/770749/shuang-jie-di-gui-you-hua-by-hu-li-hu-wa-f1k9/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
